/**
 * Dinic 算法（计算网络的最大流）
 * 
 * @author shuyuan.dai 2021-02-04
 */
class DinicAlog {
    constructor(graph) {
        this.graph = graph;
        // 每个点指向的最后一条边
        this.head = this.graph.head;
        // 每个边的同源节点的上一个边
        this.parent = this.graph.parent;
        // 每一条边指向的点
        this.V = this.graph.V;
        // 边的数量
        this.cnt = this.graph.cnt;
        // 流量
        this.streams = this.graph.streams;
    }

    /**
     * 设置一个函数介入到算法的DFS生命周期中
     * 
     * @param {*} func 介入函数 
     */
    behaviorDFS(func) {
        this.customDFSBehavior = func instanceof Function? func: () => {};
    }

    /**
     * 设置一个函数介入到算法的BFS生命周期中
     * 
     * @param {*} func 介入函数 
     */
    behaviorBFS(func) {
        this.customBFSBehavior = func instanceof Function? func: () => {};
    }

    /**
     * 深度遍历，将一条增广路径上的所有边都减去所有边残量的最小值
     * 
     * @param {*} s 源点
     * @param {*} t 汇点
     * @param {*} stream 流量
     */
    dfs(s, t, stream) {
        if(s == t) {
            return stream;
        }

        for(let i=this.head[s]; i >= 0; i = this.parent[i]) {
            // 根据构建的深度路径探索，且残量要大于0
            if(this.w[i] > 0 && this.depths[this.V[i]] == this.depths[s] + 1) {
                // 向下增广，并传递路径上的最小残量
                let di = this.dfs(this.V[i], t, Math.min(this.w[i], stream));
                // 增广成功
                if(di > 0) {
                    this.w[i] -= di;
                    this.w[i ^ 1] += di;
                    return di;
                }
            }
            this.customDFSBehavior && this.customDFSBehavior();
        }

        // 无法增广
        return 0;
    }

    /**
     * 广度遍历，构建一个树状深度路径
     * 
     * @param {*} s 源点
     * @param {*} t 汇点
     */
    bfs(s, t) {
        // 初始化深度
        this.depths = new Array(this.head.length).fill(0);
        this.depths[s] = 1; 

        let Q = [s];
        while(Q.length > 0) {
            let u = Q.shift();
            for(let i=this.head[u]; i >= 0; i = this.parent[i]) {
                if(this.w[i] > 0 && this.depths[this.V[i]] == 0) {
                    this.depths[this.V[i]] = this.depths[u] + 1;
                    Q.push(this.V[i]);
                }
            }
        }
        this.customBFSBehavior && this.customBFSBehavior();

        // 汇点的深度为0，表明汇点已经不可达
        return this.depths[t] != 0;
    }

    autoDinic(defStream = Infinity) {
        let sources = this.graph.calSourcePoint();
        let targets = this.graph.calMeetingPoint();
        let results = [];
        if(sources.length == 0 || targets.length == 0) {
            return results;
        }
        for(let i=0; i < sources.length; ++i) {
            for(let j=0; j < targets.length; ++j) {
                results.push(this.dinic(sources[i], targets[j], defStream));
            }
        }
        return results;
    }

    /**
     * Dinic算法
     * 
     * @param {*} s 源点
     * @param {*} t 汇点
     * @param {*} defStream 初始流量
     */
    dinic(s, t, defStream = Infinity) {
        // 初始化残量
        this.w = [];
        for(let i=0; i < this.streams.length; i += 2) {
            this.w[i] = this.streams[i];
            this.w[i ^ 1] = 0;
        }

        let ans = 0;
        while(this.bfs(s, t)) {
            let passStream = 0;
            while(passStream = this.dfs(s, t, defStream)) {
                ans += passStream;
            }
        }
        return [s, t, ans];
    }
}

exports.DinicAlog = DinicAlog;

